The preferred embodiments are in the field of wireless communications and are more specifically directed to automatic repeat requests from a receiving unit to indicate to a transmitting unit to re-transmit a number of data blocks that were not properly received by the receiving unit.
Advances in wireless communication technology, especially in recent years, have greatly improved not only the performance (i.e., data rate for a given error rate) at which wireless communications can be carried out, but also have enabled the realization of additional functions and services by way of wireless communications. For example, wireless broadband communication in metro area networks is now becoming commonplace. An example of one type of wider area wireless network communications is referred to as “WiMAX”, corresponding to communications carried out under IEEE Standard for Local and metropolitan area networks, Part 16: Air Interface for Fixed Broadband Wireless Access Systems (IEEE Standard 802.16-2004, and all subsequent revisions). Of course, wireless local area networks (WLAN) are also now becoming commonplace and are capable of carrying traffic at very high data rates (e.g., 100 Mbit/sec).
Networks operating under the WiMAX standard, for example, are capable of carrying out multiple types of communications. These multiple communications “services” are typically supported by modern wireless devices, including laptop computers equipped with WiMAX network adapters, palm top computers or highly capable personal digital assistants (PDAs), and modern “smartphones” that support data services. As known in the art, these modern wireless devices and systems, communicating via a WiMAX or other metro or wider area wireless network, support multiple simultaneous wireless communications sessions. Different types of such communications can have different constraints and requirements. For example, one class of such communications that can be carried out under WiMAX is voice telephony, by way of the well-known Voice over Internet Protocol (VoIP) service. VoIP communications involve constraints on the timeliness of the communications (i.e., so that a sensible back-and-forth conversation can be carried out), but can tolerate a relatively high error rate. In contrast, email services, and web browsing services over the Internet, involve less stringent time constraints, but can have higher error rate requirements.
Physically, a WiMAX metro area network is realized via base stations deployed within the physical service area with some frequency (e.g., on the order of a base station deployed every mile, to every several miles), similar to cellular telephone base stations and towers. A given base station is capable of communicating with nearby wireless client devices, typically referred to as “subscriber stations”, or often as “mobile stations” considering that these devices are typically portable computing and communications devices such as laptop or palmtop computers, smartphones, and the like. Each of the traffic flows between a mobile station and a base station is typically referred to as a “service flow”, in the context of WiMAX communications. For example, a VoIP call is carried out over one service flow, an email session is carried out over another service flow, and each web browsing session is carried out over another service flow. As evident from this discussion, multiple service flows may be carried out simultaneously between a mobile station and a base station; indeed, communications in each direction (e.g., uplink and downlink) are typically considered a separate service flows, such that bidirectional communications in an interactive web session, for example, typically constitutes two service flows.
Various communications standards include and define an automatic repeat request (ARQ) sub-protocol under which a receiving station, after receiving a sequence of blocks (or “packets”) of data, provides feedback to the transmitting station if blocks of that data were not properly received. Thus, in a given service flow, the receiving station provides feedback to the transmitting station, and from the above discussion of service flows note that for a given service flow, the receiving station may be the base station while the transmitting station is the mobile station, or conversely for a given service flow, the receiving station may be the mobile station while the transmitting station is the base station. In any event, the ARQ feedback specifies, for erroneous or lost data blocks, various message formats for the feedback messages that when received by the transmitting station, cause that station to re-transmit the improperly received (or lost) data blocks. Thus, by way of example but without limitation to the preferred embodiments detailed later, for conventional communications under the IEEE 802.16 standard, there are four different types of ARQ formats: (i) Selective ACK; (ii) Cumulative ACK; (iii) Cumulative with Selective ACK; and (iv) Cumulative ACK with Block Sequence ACK. Each of these is known in the art, but each is also described below for sake of background and with respect to Cumulative ACK with Block Sequence Ack for sake of contrast to the preferred embodiments detailed later.
In the Selective ACK ARQ format, a receiving station transmits a feedback message to a transmitting station that includes one or more (up to four) 16-bit bitmaps, where each bit in the bitmap corresponds to a respective block of data received by the receiving station and indicates, by the binary map value, whether the block was received either acceptably or in error. For example, if the binary value of 1 indicates an acceptable data block, then the binary value of 0 indicates an unacceptable (i.e., in error) data block, where at least the latter therefore is to be re-transmitted by the transmitting station once it receives and comprehends the feedback ARQ message. Using these conventions and by way of example, therefore, a 16-bit Selective ACK bitmap of 1111000011110000 indicates from the receiving station to the transmitting station that in the 16 blocks of data it received, the first set of four data blocks was acceptable, the second set of four data blocks was in error, the third set of four data blocks was acceptable, and the fourth set of four data blocks was in error. Thus, in response to the message, the transmitting station may re-transit the erroneous data blocks (i.e., the second and fourth set of blocks). Note that the Selective ACK ARQ format has at least one drawback in that it expects the transmitter and receiver windows to be synchronized. The ‘Cumulative with Selective ACK’ format (described below) avoids this problem.
In the Cumulative ACK ARQ format, a receiving station transmits a feedback message to a transmitting station that includes an identifier (e.g., sequence number) of the last data block that was satisfactorily received in a sequence of blocks. Thus, in response to the message, the transmitting station may re-transmit the sequence starting from the next block following the identified-erroneous received data block. Note that the Cumulative ACK ARQ format has at least one drawback if used in sequences that include a burst of erroneously-received data blocks in the middle of otherwise properly received data blocks. More specifically, then, consider the use of the Cumulative ACK ARQ format in a case for a sequence of 100 blocks, where the first 10 blocks are received accurately, the next 5 blocks are received in error, and the remaining 85 blocks are received accurately; in this case, then the Cumulative ACK ARQ would indicate the last error-free block before an error occurred, that is, then 10th block in the example sequence. In response, therefore, the transmitting station is caused to re-transmit the latter 90 blocks of data in the sequence, even though the latter 85 of those already were transmitted and received without errors. Thus, data bandwidth is consumed in the re-transmitting of that data.
In the Cumulative with Selective ACK format, a receiving station transmits a feedback message to a transmitting station that includes both: (1) an identifier (e.g., sequence number) of the last data block that was satisfactorily received in a sequence of blocks; and (2) one or more (up to four) 16-bit bitmaps, where each bit in a bitmap corresponds to a respective block of data received by the receiving station and indicates, by the binary value, whether the block was either acceptable or in error, where these described 16 data blocks follow the last identified block in item (1), above. In other words, this format combines the two formats detailed above. Note that the Cumulative with Selective ACK format has at least one drawback if it is used in a sequence where the error block is early in the sequence in that the bitmap therefore will only characterize the next 16 blocks following the last of the properly-received blocks in the sequence.
In the Cumulative ACK with Block Sequence ACK format, a receiving station transmits a feedback message to a transmitting station that includes an indication of the sequence number of the last in sequence correctly received block and up to 4 ACK Maps. Each ACK map includes an indication of the type of sequence used and either 14 bits in a 2 sequence variant or 15 bits in a 3 sequence variant. For either variant, these bits includes a Sequence Ack Map (“SAM”), where the Map is 2 bits for the 2 sequence variant and the Map is 3 bits for the 3 sequence variant. The state of each bit in the map indicates that a sequential number of blocks, corresponding to that bit, were received either as all valid (i.e., without error) or all invalid. For example, a binary value of 0 indicates that a corresponding sequential number of blocks were invalid, and a binary value of 1 indicates that a corresponding sequential number of blocks were valid. Thus, for the 2 sequence variant, a SAM of 01 indicates that a first sequence length SL1 of sequential blocks, corresponding to the first SAM bit value of 0, were received as invalid, and a second sequence length SL2 of sequential blocks, corresponding to the second SAM bit value of 1, were received as valid. Note that the first and second sequence lengths SL1 and SL2 are also included in the message format. Particularly, in addition to the SAM, the remaining 12 bits in the message identify two six-bit binary numbers, where each binary number thereby indicates the values of SL1 and SL2 (i.e., a value up to 31 due to the six bits). Continuing the previous example with the SAM of 01, assume also that in the remaining 12 bits the first six bits are 000111 (i.e., decimal 7) and the second six bits are 010011 (i.e., decimal 19). Thus, these values respectively indicate that SL1=7 and SL2=19. Accordingly, in combination with the SAM, this message would indicate that the receiver received a sequence of data blocks wherein the first 7 blocks were invalid while the next 19 blocks were valid. The 3 sequence variant of this format is similar, but its SAM includes three bits, each corresponding to a respective 4-bit sequence length SL1, SL2, and SL3 in the remaining 12 bits. Thus, for the 3 sequence variant, the remaining 12 bits in the message provide three 4-bit numbers that each respectively indicate one of the values of SL1, SL2, and SL3. Consider then an example of a SAM of 010, and assume also that in the remaining 12 bits the first four bits are 0011 (i.e., decimal 3, that is, SL1=3), the second four bits are 1001 (i.e., decimal 9, that is, SL2=9), and the third four bits are 0111 (i.e., decimal 7, that is, SL3=7). Thus, in combination with the SAM, this message would indicate that the receiver received a sequence of data blocks wherein the first 3 blocks in the sequence were invalid (because the first SAM bit is 0), the next 9 blocks in the sequence were valid (because the second SAM bit is 1), and the next 7 blocks in the sequence were invalid (because the third SAM bit is 0).
It is recognized in connection with the preferred embodiments that while the Cumulative ACK with Block Sequence ACK format has benefits in reporting upon certain data block sequences, it too may be unnecessarily limited in that it may be improved upon as detailed later. By way of example at this point, note that the 2 sequence variant of this format is limited in that the each sequence length SL1, is limited by the six-bit identifier, where therefore each such identifier is able to identify only up to 63 data blocks (i.e., 26−1=63), and therefore the format in its entirety is limited to describe no more than 126 data blocks (i.e., SL1+SL2≦126). Further, note that the 3 sequence variant of this format is limited in that the each sequence length SLx is limited by the four-bit identifier, where therefore each such identifier is able to identify only up to 15 data blocks (i.e., 24−1=15), and therefore the format in its entirety is limited to describe no more than 45 data blocks (i.e., SL1+SL2+SL3≦45).
Given the preceding, the preferred embodiments seek to improve upon the prior art, as demonstrated below.